// 祖先的定义：若节点 p 在节点 root 的左子树中，或 p = root，则称 root 是 p 的祖先
// 根据以上定义，若 root 是 p, q 的最近公共祖先，则只可能是以下情况之一
// 1. p 和 q 在 root 的子树中，且分列 root 的异侧
// 2. p = root，且 q 在 root 的左或右子树中
// 3. q = root，且 p 在 root 的左或右子树中

var lowestCommonAncestor = function (root, p, q) {
  if (root == null || root == p || root == q) return root;
  let left = lowestCommonAncestor(root.left, p, q);
  let right = lowestCommonAncestor(root.right, p, q);
  if (left == null && right == null) return null;
  if (left == null) return right;
  if (right == null) return left;
  return root;
}